package uestc.lj.midPromotion.dfs;

import java.util.HashMap;
import java.util.Stack;

/**
 * @Author:Crazlee
 * @Date:2021/11/30
 */
public class Code03_MaxSumInTree {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int val) {
			value = val;
		}
	}

	public static int maxSumInTree(Node root) {
		return process(root, 0);
	}

	private static int process(Node node, int prev) {
		if (node == null) {
			return Integer.MIN_VALUE;
		}
		if (node.left == null && node.right == null) {
			return prev + node.value;
		}
		int leftValue = process(node.left, prev + node.value);
		int rightValue = process(node.right, prev + node.value);
		return Math.max(leftValue, rightValue);
	}

	public static int maxSumUnrecursive(Node head) {
		int max = 0;
		HashMap<Node, Integer> sumMap = new HashMap<>();
		if (head != null) {
			Stack<Node> stack = new Stack<>();
			stack.add(head);
			sumMap.put(head, head.value);
			while (!stack.isEmpty()) {
				head = stack.pop();
				if (head.left == null && head.right == null) {
					max = Math.max(max, sumMap.get(head));
				}
				if (head.right != null) {
					sumMap.put(head.right, sumMap.get(head) + head.right.value);
					stack.push(head.right);
				}
				if (head.left != null) {
					sumMap.put(head.left, sumMap.get(head) + head.left.value);
					stack.push(head.left);
				}
			}
		}
		return max;
	}
}
